package week_10;

public class CountBits_338 {
    public int[] countBits2(int n) {
        int[] arr = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int tmp = i;
            while (tmp != 0) {
                count++;
                tmp -= tmp & -tmp;
            }
            arr[i] = count;
        }
        return arr;
    }

    /**
     * 奇偶分类
     * 对于所有的数字，只有两类：
     * 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
     *           举例：
     *          0 = 0       1 = 1
     *          2 = 10      3 = 11
     * 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
     *            举例：
     *           2 = 10       4 = 100       8 = 1000
     *           3 = 11       6 = 110       12 = 1100
     * 另外，0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了
     */

    public int[] countBits(int n) {
        int[] arr=new int[n+1];
        arr[0]=0;

        for(int i=1;i<=n;i++){
            // 奇数
            if((i&1)==1){
                arr[i]=arr[i-1]+1;
            }
            // 偶数
            if((i&1)==0){
                arr[i]=arr[i/2];
            }
        }
        return arr;
    }

    /**
     * 动归思路：最高有效位
     * 很复杂
     */
    public int[] countBits3(int n) {
        int[] arr=new int[n+1];
        arr[0]=0;
        int hightBit=0;
        for(int i=1;i<=n;i++){
            if(i==(i&-i)){
                hightBit=i;
            }
            arr[i] =arr[i-hightBit] +1;
        }
        return arr;
    }

}
